/*
 * \file CplexColorRD.h
 * \brief Clase CplexColorRD, implementación de StabSolver para Cplex
 *
 *  Created on: Jul 29, 2014
 *      Author: correa
 */

#ifndef CPLEXCOLORRD_H_
#define CPLEXCOLORRD_H_

#include <CplexStabSolver.h>
#include <RepSearchTree.h>
#include <ColorBranching.h>
#include <vector>

/*!
 * \class CplexColorRD
 * \brief Implementación de StabSolver para Cplex
 */
class CplexColorRD : public StabSolver
{
protected:
	Grafo& 						_grafo;
	const int					_k;
	MatrixOfRepresentaciones& 	_mapa;
	ArrayOfRepresentaciones 	_array;

	VertexSet 					_auxset;

	int cliqueMaximal(const VertexSet * subgrafo, VertexSet * c);
	int cliqueMaximal(const VertexSet * subgrafo, VertexSet * c, Lista &orden);

public:
	CplexColorRD(Grafo &grafo, MatrixOfRepresentaciones& mapa, int k=0) : _grafo(grafo), _k(k > 0 ? k : grafo.getN()), _mapa(mapa), _array(_mapa), _auxset(grafo.getN()) {};
	~CplexColorRD() {};
	/*!
	 * \fn DoubleValueArray* solve(SeparatorParameters& parameters)
	 * \brief  Ejecuta el algoritmo entero para cplex
	 *
	 * \param parameters Para controlar ejecución
	 */
	virtual DoubleValueArray* solve(SeparatorParameters& parameters);
	/*!
	 * \fn DoubleValueArray* solveLinearRelaxation()
	 * \brief Ejecuta la relajacion lineal.
	 */
	virtual DoubleValueArray* solveLinearRelaxation();
};

inline int CplexColorRD::cliqueMaximal(const VertexSet * subgrafo, VertexSet * c)
{
	int v;
	int ret = 0;
	VertexSet candidatos(*subgrafo);

	while ((v = candidatos.least()) >= 0) {
		c->add(v);
		ret++;
		candidatos.retainAll(_grafo.vecinos(v));
	}

	return ret;
}

inline int CplexColorRD::cliqueMaximal(const VertexSet * subgrafo, VertexSet * c, Lista &orden)
{
	int v;
	int ret = 0;
	VertexSet candidatos(_grafo.getN());
	candidatos.copyAll(*subgrafo);

	int i;
	for (i = 0; i < orden.cantidad(); i++) {
		v = orden[i];
		if (candidatos.contains(v))
		{
			c->add(v);
			ret++;
			candidatos.retainAll(_grafo.vecinos(v));
		}
	}

	return ret;
}

class CplexRepSolucion : public CplexSolucion {
protected:
	ArrayOfRepresentaciones& 	_array;

	CplexRepSolucion(CplexRepSolucion& sol, int n) : CplexSolucion(sol._model, sol._x, n), _array(sol._array) {};

public:
	CplexRepSolucion(IloCplex::ControlCallbackI * model, IloNumVarArray& x, ArrayOfRepresentaciones& array) : CplexSolucion(model, x), _array(array) {};
	~CplexRepSolucion() {};

	Solucion * newInstance(int r, int n);
};

class CplexRepSubSolucion : public CplexRepSolucion {
	friend class CplexRepSolucion;

	int		_rep;
	double 	_fracval;
	double	_value;

	CplexRepSubSolucion(CplexRepSolucion& repSol, int rep, int n);
public:
	~CplexRepSubSolucion() {};

	const double operator [](int i) const;
	double operator [](int i);
	double value();
	void print() const;
};

inline Solucion * CplexRepSolucion::newInstance(int r, int n) {
	return new CplexRepSubSolucion(*this, r, n);
}

inline CplexRepSubSolucion::CplexRepSubSolucion(CplexRepSolucion& repSol, int rep, int n) : CplexRepSolucion(repSol, n), _rep(rep) {
	_nfrac = 0;
	_nzeroes = 0;
	_value = CplexSolucion::operator [](_array[_rep][_rep]);
	_fracval = 1.0-_value;
	_fracVertices.add(_rep);
	if (_fracval >= 1.0-1.0e-5)
	{
		_nzeroes++;
		_fracval = 1.0;
	}
	else
	{
		_nfrac++;
	}
	for (int i = _rep+1; i < _n; i++) {
		if (_array[_rep][i] < 0)
			_nzeroes++;
		else {
			double val = CplexSolucion::operator [](_array[_rep][i]);
			_value += val;
			if (val < _fracval-1.0e-5) {
				_fracVertices.add(i);
				if (val < 1.0e-5)
					_nzeroes++;
				else
					_nfrac++;
			}
		}
	}
}

inline const double CplexRepSubSolucion::operator [](int i) const
{
//	cout << "rep=" << _rep << " i=" << i << " index=" << _array[_rep][i] << endl;
	if (i == _rep)
		return 0.0;
	i = _array[_rep][i];
	if (i < 0 || _fracval == 0.0)
		return 0.0;
	return CplexSolucion::operator [](i)/_fracval;
}

inline double CplexRepSubSolucion::operator [](int i)
{
	if (i == _rep)
		return 0.0;
	i = _array[_rep][i];
	if (i < 0 || _fracval == 0.0)
		return 0.0;
	return CplexSolucion::operator [](i)/_fracval;
}

inline double CplexRepSubSolucion::value()
{
	return _value;
}

inline void CplexRepSubSolucion::print() const
{
	cout << "(fracVal=" << _fracval << ") ";
	CplexSolucion::print();
}

class CplexRepSearchTree : public RepSearchTree<RepRangeDesigualdad>
{
	class ParejaData : public IloCplex::MIPCallbackI::NodeData
	{
		friend class CplexRepSearchTree;

		Pareja *	_pareja;

		ParejaData(int u, int v, Pareja * p, TipoPareja t) : _pareja(new Pareja(u, v, p, t)) {};
		ParejaData(Pareja * p) : _pareja(p) {};
		~ParejaData()
		{
			if (_pareja->getTipo() != TipoPareja::_ROOT && !_pareja->hayHijos())
				delete _pareja;
		};
		void print() { _pareja->print(); };
	};

	IloNumVarArray&				_x;
	MatrixOfRepresentaciones& 	_mapa;
	ArrayOfRepresentaciones 	_array;

public:
	CplexRepSearchTree(Grafo &grafo, IloNumVarArray& x, MatrixOfRepresentaciones& mapa, ArrayOfRepresentaciones& array) : RepSearchTree<RepRangeDesigualdad>(grafo), _x(x), _mapa(mapa), _array(array) {};
	~CplexRepSearchTree() {};

	Desigualdad * newDesigualdad() { cout << "RepSearchTree: newDesigualdad not allowed." << endl; throw(-1); };
	Desigualdad * newDesigualdad(const Desigualdad& otra) { cout << "RepSearchTree: newDesigualdad not allowed." << endl; throw(-1); };
	DesigualdadArray<RepRangeDesigualdad> * newDesigualdadArray() { return new CplexRepDesigualdad(_x, _mapa, _array); };
	DesigualdadArray<RepRangeDesigualdad> * newDesigualdadArray(const DesigualdadArray<RepRangeDesigualdad>& otra) { return new CplexRepDesigualdad((CplexRepDesigualdad&) otra); };

	IloCplex::MIPCallbackI::NodeData * root() { return new ParejaData(&_root); }
	IloCplex::MIPCallbackI::NodeData * subir(int v, IloCplex::MIPCallbackI::NodeData * p) { return new ParejaData(v, v, p == NULL ? &_root : ((ParejaData *) p)->_pareja, TipoPareja::_FIXASREP); }
	IloCplex::MIPCallbackI::NodeData * bajar(int v, IloCplex::MIPCallbackI::NodeData * p) { return new ParejaData(v, v, p == NULL ? &_root : ((ParejaData *) p)->_pareja, TipoPareja::_FIXASNOREP); }
	IloCplex::MIPCallbackI::NodeData * ligar(int u, int v, IloCplex::MIPCallbackI::NodeData * p) { return new ParejaData(u, v, p == NULL ? &_root : ((ParejaData *) p)->_pareja, TipoPareja::_CONNECT); }
	IloCplex::MIPCallbackI::NodeData * identificar(int u, int v, IloCplex::MIPCallbackI::NodeData * p) { return new ParejaData(u, v, p == NULL ? &_root : ((ParejaData *) p)->_pareja, TipoPareja::_IDENT); }
	bool dominados(int v, IloCplex::MIPCallbackI::NodeData * p, IloRangeArray& constraints);
	void configGrafo(IloCplex::MIPCallbackI::NodeData * p) { RepSearchTree<RepRangeDesigualdad>::configGrafo(((ParejaData *) p)->_pareja); };
	void print(IloCplex::MIPCallbackI::NodeData * p) { ((ParejaData *) p)->print(); };
};

class CplexRepBranching : public RepBranching<RepRangeDesigualdad>
{
	CplexRepSearchTree&	_tree;

protected:
	Desigualdad * newDesigualdad() { cout << "RepBranching: newDesigualdad not allowed." << endl; throw(-1); };
	Desigualdad * newDesigualdad(const Desigualdad& otra) { cout << "RepBranching: newDesigualdad not allowed." << endl; throw(-1); };
	DesigualdadArray<RepRangeDesigualdad> * newDesigualdadArray() { return _tree.newDesigualdadArray(); };
	DesigualdadArray<RepRangeDesigualdad> * newDesigualdadArray(const DesigualdadArray<RepRangeDesigualdad>& otra) { return _tree.newDesigualdadArray(otra); };

public:
	CplexRepBranching(Grafo &grafo, CplexRepSearchTree& t, ReservaClique * reserva=NULL) : RepBranching<RepRangeDesigualdad>(grafo, reserva), _tree(t) {};
	~CplexRepBranching() {};
};

class CplexSubRepBranching : public CplexBranching
{
	int							_rep;
	MatrixOfRepresentaciones& 	_mapa;
	ArrayOfRepresentaciones&	_array;

protected:
	Desigualdad * newDesigualdad() { return new CplexSubRepDesigualdad(_rep, _x, _mapa, _array); };
	Desigualdad * newDesigualdad(const Desigualdad& otra) { return new CplexSubRepDesigualdad((CplexSubRepDesigualdad&) otra); };

public:
	CplexSubRepBranching(Grafo &grafo, int r, IloNumVarArray& x, MatrixOfRepresentaciones& mapa, ArrayOfRepresentaciones& array, const VertexSet& subgrafo, ReservaClique * reserva=NULL) : CplexBranching(grafo, x, subgrafo, reserva), _rep(r), _mapa(mapa), _array(array) {};
	~CplexSubRepBranching() {};
};

inline bool CplexRepSearchTree::dominados(int v, IloCplex::MIPCallbackI::NodeData * p, IloRangeArray& constraints)
{
	bool ret = false;
	list<DesigualdadArray<RepRangeDesigualdad> *>& desigualdades = RepSearchTree<RepRangeDesigualdad>::dominadosSiRep(v, ((ParejaData *) p)->_pareja);
	while (!desigualdades.empty())
	{
		ret = true;
		CplexRepDesigualdad * d = (CplexRepDesigualdad *) desigualdades.back();
		desigualdades.pop_back();
		constraints.add(*d);
//		d->print();
		delete d;
	}

	return ret;
}

class CplexRepSeparator : public CplexSeparator
{
	int							_rep;
	MatrixOfRepresentaciones& 	_mapa;
	ArrayOfRepresentaciones& 	_array;

	Desigualdad * newDesigualdad() { return new CplexSubRepDesigualdad(_rep, _x, _mapa, _array); };
	Desigualdad * newDesigualdad(const Desigualdad& otra) { return new CplexSubRepDesigualdad((CplexSubRepDesigualdad&) otra); };

public:
	CplexRepSeparator(Grafo &grafo, int r, IloNumVarArray& x, MatrixOfRepresentaciones& mapa, ArrayOfRepresentaciones& array, SeparatorParameters &parametros) : CplexSeparator(grafo, x, parametros), _rep(r), _mapa(mapa), _array(array) {};
	~CplexRepSeparator() {};
	void configGrafo(IloCplex::MIPCallbackI::NodeData * data);
};

typedef struct {
	IloCplex::MIPCallbackI::NodeData * lastNode;
} RepCutGeneratorHistory;

class Subproblema
{
	const Grafo&				_grafo;
	DiGrafo&					_order;
	ArrayOfRepresentaciones& 	_array;
	int 						_nh;
	VertexSet 					_H;
	VertexSet 					_Hbar;
	int							_tamanho;
	int							_nreps;
	VertexSet					_rep;
	VertexSet					_auxset;
	VertexSet 					_SH;
	VertexSet 					_HS;
	int *						_degree;
	IloNumArray					_solucionEntera;

private:
	bool isActiva(int v, IloNumVarArray& x);
	void activar(int v, IloNumVarArray& x);
	void desactivar(int v, IloNumVarArray& x);
	void greedify(IloRangeArray& constraints, IloNumVarArray& x, IloNumVarArray& y);
	void addNosymConst(int r1, int r2, int v, IloRangeArray& constraints, IloNumVarArray& x);

public:
	Subproblema(IloEnv env, Grafo& g, VertexSet& hb, DiGrafo& o, ArrayOfRepresentaciones& array, int sz);
	~Subproblema();

	int assignx(IloCplex& cplex, IloNumVarArray& x, IloNumVarArray& y);
	int buscarYDesactivar(IloNumVarArray& x, IloNumVarArray& y);
	void activarTodos(IloNumVarArray& x, IloNumVarArray& y);
	int addCandidato(int r, IloRangeArray& constraints, IloNumVarArray& x, IloNumVarArray& y);
	int addCandidato(IloRangeArray& constraints, IloNumVarArray& x, IloNumVarArray& y);
	int extendWithStab(int r, IloRangeArray& constraints, IloNumVarArray& x, IloNumVarArray& y);
	int extendWithStab(IloRangeArray& constraints, IloNumVarArray& x, IloNumVarArray& y);
	void addChromoBoundConst(int objValue, IloRangeArray& constraints, IloNumVarArray& x, IloNumVarArray& y);
	void addChromoConst(int objValue, IloRangeArray& constraints, IloNumVarArray& x);
	void addCliqueConst(VertexSet& clique, IloRangeArray& constraints, IloNumVarArray& x);
	void addNosymConsts(int r1, IloRangeArray& constraints, IloNumVarArray& x);
	void createNosingletonConst(int v, IloRange& constraint, IloNumVarArray& x);
	IloNumArray& solucionEntera();
	int tamanoMuneca() { return _nh; };
	int tamano() { return _tamanho; };
	int ncolores() { return _nreps; };

	void print(IloNumVarArray& y);
};

class CplexStabColorModel : public IloCplex {
	int _n;
	IloNumVarArray _x;
	IloNumVarArray _y;
	vector<CplexRepSeparator *> _separator;
	CplexRepBranching * _branching;
	CplexRepSearchTree * _tree;

public:
	CplexStabColorModel(IloModel model, Grafo& _grafo, const int _k, MatrixOfRepresentaciones& _mapa, ArrayOfRepresentaciones& _array, SeparatorParameters& parameters);
	~CplexStabColorModel();

	IloNumVarArray& getX() { return _x; };
	IloNumVarArray& getY() { return _y; };
	CplexRepSeparator * separator(int r) { return _separator[r]; };
	IloBool solve() { bool ret = IloCplex::solve(); _tree->configGrafo(_tree->root()); return ret; };
};

#endif /* CPLEXCOLORRD_H_ */
